//The MIT License
//
//Copyright (c) 2009 nodchip
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in
//all copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//THE SOFTWARE.
package tv.dyndns.kishibe.server.relevance;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.ByteArrayOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.net.URL;
import java.net.URLConnection;
import java.text.Normalizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.zip.DeflaterOutputStream;
import java.util.zip.GZIPInputStream;
import java.util.zip.InflaterInputStream;

public class Trie {
	private static final int displayStep = 1024 * 1024;
	private static final int bufferSize = 64 * 1024;
	private int[][] array;

	public Trie() throws Exception {
		final ObjectInputStream inputStream = new ObjectInputStream(new InflaterInputStream(new BufferedInputStream(new FileInputStream("/var/www/html/qmaclone/jawiki-latest-all-titles-in-ns0.dat"))));
		array = (int[][]) inputStream.readObject();
		inputStream.close();
	}

	public Trie(String[] words) throws Exception {
		create(words);
	}

	private void create(String[] words) throws Exception {
		final List<Map<Integer, Integer>> trie = new ArrayList<Map<Integer, Integer>>();
		trie.add(new TreeMap<Integer, Integer>());
		for (String word : words) {
			addWord(word, trie);
		}

		array = new int[trie.size()][];
		for (int nodeIndex = 0; nodeIndex < trie.size(); ++nodeIndex) {
			array[nodeIndex] = new int[trie.get(nodeIndex).size() * 2];
			int leafIndex = 0;
			for (Entry<Integer, Integer> entry : trie.get(nodeIndex).entrySet()) {
				array[nodeIndex][leafIndex++] = entry.getKey();
				array[nodeIndex][leafIndex++] = entry.getValue();
			}
		}
	}

	private void addWord(String word, List<Map<Integer, Integer>> trie) {
		word = Normalizer.normalize(word, Normalizer.Form.NFKC);

		int currentNode = 0;
		for (char c : word.toCharArray()) {
			if (trie.get(currentNode).containsKey(c & 0xffff)) {
				currentNode = trie.get(currentNode).get(c & 0xffff);
			} else {
				trie.get(currentNode).put(c & 0xffff, trie.size());
				currentNode = trie.size();
				trie.add(new TreeMap<Integer, Integer>());
			}
		}
		trie.get(currentNode).put(0, 0);
	}

	public void parse(String string, List<String> words) {
		string = Normalizer.normalize(string, Normalizer.Form.NFKC);

		final char[] s = string.toCharArray();
		final int n = s.length;
		final int[] memo = new int[n + 1];
		final int[] edge = new int[n + 1];

		for (int startIndex = 0; startIndex < n; ++startIndex) {
			// 一致する文字が無い場合は何もせずに1マス進む
			if (memo[startIndex + 1] < memo[startIndex]) {
				memo[startIndex + 1] = memo[startIndex];
				edge[startIndex + 1] = 0;
			}

			int nodeIndex = 0;
			for (int currentIndex = startIndex; currentIndex < n; ++currentIndex) {
				// 葉が無かったら
				if (array[nodeIndex].length == 0) {
					break;
				}

				// 終端文字が見つかったら
				if (array[nodeIndex][0] == 0 && currentIndex - startIndex != 1) {
					final int cost = memo[startIndex] + (currentIndex - startIndex) * (currentIndex - startIndex);
					if (memo[currentIndex] < cost) {
						memo[currentIndex] = cost;
						edge[currentIndex] = currentIndex - startIndex;
					}
				}

				// 次の葉に移動する
				int c = s[currentIndex] & 0xffff;
				int l = 0;
				int r = array[nodeIndex].length / 2;
				while (l + 1 < r) {
					final int m = (l + r) >> 1;
					// lowerBound
					if (array[nodeIndex][m * 2] <= c) {
						l = m;
					} else {
						r = m;
					}
				}

				if (l == array[nodeIndex].length / 2 || array[nodeIndex][l * 2] != c) {
					break;
				}

				nodeIndex = array[nodeIndex][l * 2 + 1];
			}
		}

		// 動的計画法のトラックバック
		int currentIndex = n;
		while (currentIndex > 0) {
			if (edge[currentIndex] == 0) {
				currentIndex--;
			} else {
				words.add(string.substring(currentIndex - edge[currentIndex], currentIndex));
				currentIndex -= edge[currentIndex];
			}
		}
		Collections.reverse(words);
	}

	private static final String initials = "あぁかがさざただなはばぱまやゃらわゎいぃきぎしじちぢにひびぴみりゐうぅくぐすずつづっぬふぶぷむゆゅるえぇけげせぜてでねへべぺめれゑおぉこごそぞとどのほぼぽもよょろをん";

	public static void main(String[] args) throws Exception {
		Set<String> words = new HashSet<String>();

		int counter = 0;

		// 日本語版Wikipediaタイトル一覧
		{
			final Scanner scanner = new Scanner(new BufferedInputStream(new GZIPInputStream(new BufferedInputStream(new FileInputStream("/var/www/html/qmaclone/jawiki-latest-all-titles-in-ns0.gz")))), "utf-8");
			while (scanner.hasNextLine()) {
				String line = new String(scanner.nextLine().replaceAll("\n", ""));
				if (line.isEmpty()) {
					continue;
				}

				line = line.replaceAll("_", "");

				words.add(Normalizer.normalize(line, Normalizer.Form.NFKC));

				if (++counter % 10000 == 0) {
					System.out.println("Wikipedia: " + counter);
				}
			}
			scanner.close();
		}

		// ニコニコ大百科
		{
			String indexHtml = download("http://dic.nicovideo.jp/m/a/a", "utf-8");
			final Matcher matcher = Pattern.compile("<a href=\"(/m/yp/.+?)\">").matcher(indexHtml);
			while (matcher.find()) {
				final String url = "http://dic.nicovideo.jp" + matcher.group(1);
				final String html = download(url, "utf-8");
				final Matcher matcher2 = Pattern.compile("<a href=\"/a/.+?\">(.+?)</a>").matcher(html);
				while (matcher2.find()) {
					String word = matcher2.group(1);
					word = word.replaceAll("_", "");
					words.add(Normalizer.normalize(word, Normalizer.Form.NFKC));

					if (++counter % 10000 == 0) {
						System.out.println("Nico: " + counter);
					}
				}

				Thread.sleep(100);
			}
		}

		// // はてなキーワード
		// for (char initial : initials.toCharArray()) {
		// int maxPageIndex = 1;
		// for (int pageIndex = 1; pageIndex <= maxPageIndex; ++pageIndex) {
		// final String html = download(String.format("http://d.hatena.ne.jp/keywordlist?s=furigana&word=^%c&of=%d", initial, (pageIndex - 1) * 20), "euc-jp");
		// final Matcher matcher = Pattern.compile("<a href=\"keywordlist\\?of=.+?&s=furigana&word=.+?\">(.+?)</a>").matcher(html);
		// while (matcher.find()) {
		// maxPageIndex = Math.max(maxPageIndex, Integer.parseInt(matcher.group(1)));
		// }
		//
		// final Matcher matcher2 = Pattern.compile("<a href=\"/keyword/.+?\" class=\"keyword\">(.+?)</a>").matcher(html);
		// while (matcher2.find()) {
		// String word = matcher2.group(1);
		// words.add(Normalizer.normalize(word, Normalizer.Form.NFKC));
		//
		// if (++counter % 10000 == 0) {
		// System.out.println("Wikipedia: " + counter);
		// }
		// }
		//
		// Thread.sleep(100);
		// }
		//
		// }

		final String[] wordsArray = words.toArray(new String[0]);
		words = null;
		final Trie trie = new Trie(wordsArray);

		final List<String> extractedWords = new ArrayList<String>();
		trie.parse("少年時代から無鉄砲な江戸っ子の坊っちゃんと、肉親から疎んじられる彼に無償の愛を注ぐ女中である清の描写から『坊っちゃん』の物語は幕を開く。坊っちゃんは両親と死別後、清とも離れ、四国の旧制中学校に数学の教師として赴任する。着任早々、校長には狸、教頭には赤シャツ、画学の教師には野だいこ、英語の教師にはうらなり、数学の主任教師には山嵐と、それぞれにあだ名を付けた。坊っちゃんは授業の時に生徒達から、てんぷらそばを四杯食べた件等の私事について執拗に冷やかされる。また初めての宿直の夜には、寄宿生達から蒲団の中に大量のバッタ（厳密にはイナゴ）を入れられる等の嫌がらせを受け、激怒して、何としても犯人を突き止めようとしたため、大事になってしまう。坊っちゃんは赤シャツとその腰巾着である野だいこから、生徒による嫌がらせは山嵐の扇動によるものであると婉曲的に吹き込まれ、一時は真に受けてしまう。しかし、後日の職員会議において、先の寄宿生の不祥事に坊っちゃんが毅然とした措置を主張したところ、狸をはじめとする事なかれ主義の職員達は取り合ってくれなかったのに対し、山嵐だけが坊っちゃんを支持してくれた。お互いに対する誤解は解けていき、坊っちゃんと山嵐とは、かえって強い友情で結ばれるようになる。うらなりには、マドンナとあだ名される婚約者がいたが、赤シャツがマドンナへの横恋慕から、お人好しのうらなりを体良く延岡に左遷したという事実を知り、坊っちゃんは義憤にかられる。実は山嵐も、赤シャツの横恋慕を糾弾したため、逆恨みされていたのであった。日露戦争の祝勝会の日に、坊っちゃんと山嵐は赤シャツの謀略により、中学校と師範学校の生徒同士の乱闘騒ぎに巻き込まれた上、いわれ無き生徒扇動の罪を着せられ、山嵐が辞職に追い込まれる。卑劣な仕打ちに憤激した坊っちゃんと山嵐は、赤シャツと野だいこの不祥事を暴くための監視を始め、ついに芸者遊び帰りの赤シャツと野だいこを取り押さえる。そして芸者遊びについて詰問するも、しらを切られたため、業を煮やし、激しく暴行を加えた。即刻辞職した坊っちゃんは、帰郷後、街鉄（現在の都電）の技手となって、再び、清と同居生活を始めるが、清が亡くなり、遺言通り小日向の養源寺に葬った事を記して、『坊っちゃん』の物語は幕を閉じる。", extractedWords);
		for (String word : extractedWords) {
			System.out.println(word);
		}

		final ObjectOutputStream outputStream = new ObjectOutputStream(new DeflaterOutputStream(new BufferedOutputStream(new FileOutputStream("/var/www/html/qmaclone/jawiki-latest-all-titles-in-ns0.dat"))));
		outputStream.writeObject(trie.array);
		outputStream.close();
	}

	private static String download(String url, String encoding) throws Exception {
		System.out.println("downloading : " + url);
		URLConnection connection = new URL(url).openConnection();
		connection.setDefaultUseCaches(true);
		connection.setUseCaches(true);
		final InputStream inputStream = new BufferedInputStream(connection.getInputStream());
		connection.connect();
		final int contentLength = connection.getContentLength();
		final ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
		int totalSize = 0;
		int displaySize = displayStep;
		while (true) {
			byte[] bs = new byte[bufferSize];
			final int readSize = inputStream.read(bs);
			if (readSize == -1) {
				break;
			}
			outputStream.write(bs, 0, readSize);
			totalSize += readSize;

			if (displaySize <= totalSize) {
				System.out.println(totalSize + " / " + contentLength);
				displaySize += displayStep;
			}
		}
		System.out.println(totalSize + " / " + contentLength);
		inputStream.close();

		final byte[] result = outputStream.toByteArray();
		return new String(result, encoding);
	}
}
